package 牛客网_N.查找_递归_排序_贪心.最大差值;

import java.util.Scanner;
/**
 * 有一个长为n的数组A，求满足0≤a≤b<n的A[b]-A[a]的最大值。
给定数组A及它的大小n，请返回最大差值。
测试样例：
[10,5],2
返回：0
 * @author x
 * @summary
 */
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int n = Integer.parseInt(in.nextLine());
		String str = in.nextLine();
		String[] dataStr = str.split(" ");
		int[] A = new int[dataStr.length];
		for(int i = 0; i < dataStr.length; i++){
			A[i] = Integer.parseInt(dataStr[i]);
		}
		System.out.println(getDis(A, n));
	}
	
	/**
	 * 动态规划2
	 */
	public static int getDis3(int[] A, int n){
		int[] dp = new int[A.length];
		dp[0] = 0;
		int min = A[0];
		int max = 0;
		for(int i = 1; i < A.length; i++){
			dp[i] = Math.max(dp[i-1], A[i] - min);
			if(dp[i] > max) max = dp[i];
			if(A[i] < min) min = A[i];
		}
		return max;
	}
	
	/**
	 * 动态规划
	 * @param a
	 * @param n
	 * @return
	 */
	public static int getDis(int[] A, int n) {
		int[] dp = new int[A.length];
		dp[0] = 0;
		int max = 0;
		for(int i = 1; i < A.length; i++){
			dp[i] = Math.max(0, dp[i-1] + A[i] - A[i-1]);
			if(dp[i] > max) max = dp[i];
		}
		return max;
	}
	
	/**
	 * 贪心 每遍历一个数，与最小值相减，得差，比最大差值大则赋为最大差值，
	 * 每个数与最小值比较，更小则赋为最小值。
	 */
	public static int getDis2(int[] A, int n){
		int min = A[0];
		int max = 0;
		for(int i = 1; i < A.length; i++){
			int dis = A[i] - min ;
			if(dis > max) max = dis;
			if(A[i] < min ) min = A[i];
		}
		return max;
	}
}
